/*
 * @(#)SecureRandom.java	1.20 01/12/12
 *
 * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package java.security;

import java.util.*;

/**
 * <p>This class provides a crytpographically strong pseudo-random number
 * generator based on the SHA-1 hash algorithm.
 *
 * <p>The calls inherited from Random will be implemented in terms of the
 * strengthened functionality.
 *
 * @see java.util.Random
 *
 * @version 1.2 96/09/15
 * @author Benjamin Renaud
 * @author Josh Bloch
 * @author Gadi Guy
 */

public class SecureRandom extends Random {

	/**
	 * Used by the empty constructor to seed the SecureRandom under
	 * construction.
	 */
	private static SecureRandom seeder;
	private static final int DIGEST_SIZE = 20;
	private transient MessageDigest digest;
	private byte[] state;
	private byte[] remainder;
	private int remCount;

	/**
	 * This empty constructor automatically seeds the generator.  We attempt
	 * to provide sufficient seed bytes to completely randomize the internal
	 * state of the generator (20 bytes).  Note, however, that our seed
	 * generation algorithm has not been thoroughly studied or widely deployed.
	 *
	 * <p>The first time this constructor is called in a given Virtual Machine,
	 * it may take several seconds of CPU time to seed the generator, depending
	 * on the underlying hardware.  Successive calls run quickly because they
	 * rely on the same (internal) pseudo-random number generator for their
	 * seed bits.
	 *
	 * <p>The seeding procedure implemented by this constructor ensures that
	 * the sequence of pseudo-random bytes produced by each SecureRandom
	 * instance yields no useful information about the byte-sequence produced
	 * by any other instance.  If however, the user wishes to produce multiple
	 * instances with truly unrelated seeds, the following code yields
	 * the desired result (at substantial CPU cost per instance!):<p>
	 *
	 * <pre>
	 * SecureRandom rnd = new SecureRandom(SecureRandom.getSeed(20));
	 * </pre>
	 */
	public SecureRandom() {
		this(nextSeed());
	}

	/**
	 * This call, used exclusively by the empty constructor, returns 20 seed
	 * bytes to seed the SecureRandom instance under construction.  The first
	 * time this method is called, creates a class-wide generator-generator.
	 * This involves generating 20 "real-random" bytes with getSeed, which is
	 * very time consuming!
	 */
	private synchronized static byte[] nextSeed() {
		if (seeder == null) {
			seeder = new SecureRandom(getSeed(20));
			seeder.setSeed(SeedGenerator.getSystemEntropy());
		}

		byte seed[] = new byte[20];
		seeder.nextBytes(seed);
		return seed;
	}


	/**
	 * This constructor uses a user-provided seed in preference to the
	 * self-seeding algorithm referred to in the empty constructor
	 * description. It may be preferable to the empty constructor if the
	 * caller has access to high-quality random bytes from some physical
	 * device (for example, a radiation detector or a noisy diode).
	 *
	 * @param seed the seed.
	 */
	public SecureRandom(byte seed[]) {
		/*
		 * This call to our superclass constructor will result in a call
		 * to our own setSeed method, which will return immediately when
		 * it is passed zero.
		 */
		super(0);

		try {
			digest = MessageDigest.getInstance("SHA");
		} catch (NoSuchAlgorithmException e) {
			throw new InternalError("internal error: SHA-1 not available.");
		}

		setSeed(seed);
	}

	/**
	 * Reseeds this random object. The given seed supplements, rather than
	 * replaces, the existing seed. Thus, repeated calls are guaranteed
	 * never to reduce randomness.
	 *
	 * @param seed the seed.
	 */
	synchronized public void setSeed(byte[] seed) {
		if (state != null) {
			digest.update(state);
			for (int i = 0; i < state.length; i++)
				state[i] = 0;
		}
		state = digest.digest(seed);
	}

	/**
	 * Reseeds this random object, using the eight bytes contained
	 * in the given <code>long seed</code>. The given seed supplements,
	 * rather than replaces, the existing seed. Thus, repeated calls
	 * are guaranteed never to reduce randomness.
	 *
	 * <p>This method is defined for compatibility with
	 * <code>java.util.Random</code>.
	 *
	 * @param seed the seed.
	 */
	public void setSeed(long seed) {
		/*
		 * Ignore call from super constructor (as well as any other calls
		 * unfortunate enough to be passing 0).  It's critical that we
		 * ignore call from superclass constructor, as digest has not
		 * yet been initialized at that point.
		 */
		if (seed != 0)
			setSeed(longToByteArray(seed));
	}

	private static void updateState(byte[] state, byte[] output) {
		int last = 1;
		int v = 0;
		byte t = 0;
		boolean zf = false;

		// state(n + 1) = (state(n) + output(n) + 1) % 2^160;
		for (int i = 0; i < state.length; i++) {
			// Add two bytes
			v = (int)state[i] + (int)output[i] + last;
			// Result is lower 8 bits
			t = (byte)v;
			// Store result. Check for state collision.
			zf = zf | (state[i] != t);
			state[i] = t;
			// High 8 bits are carry. Store for next iteration.
			last = v >> 8;
		}

		// Make sure at least one bit changes!
		if (!zf)
			state[0]++;
	}

	/**
	 * Generates a user-specified number of random bytes.  This method is
	 * used as the basis of all random entities returned by this class
	 * (except seed bytes).  Thus, it may be overridden to change the
	 * behavior of the class.
	 *
	 * @param bytes the array to be filled in with random bytes.
	 */

	synchronized public void nextBytes(byte[] result) {
		int index = 0;
		int todo;
		byte[] output = remainder;

		// Use remainder from last time
		int r = remCount;
		if (r > 0) {
			// How many bytes?
			todo = (result.length - index) < (DIGEST_SIZE - r) ?
					(result.length - index) : (DIGEST_SIZE - r);
			// Copy the bytes, zero the buffer
			for (int i = 0; i < todo; i++) {
				result[i] = output[r];
				output[r++] = 0;
			}
			remCount += todo;
			index += todo;
		}

		// If we need more bytes, make them.
		while (index < result.length) {
			// Step the state
			digest.update(state);
			output = digest.digest();
			updateState(state, output);

			// How many bytes?
			todo = (result.length - index) > DIGEST_SIZE ?
					DIGEST_SIZE : result.length - index;
			// Copy the bytes, zero the buffer
			for (int i = 0; i < todo; i++) {
				result[index++] = output[i];
				output[i] = 0;
			}
			remCount += todo;
		}

		// Store remainder for next time
		remainder = output;
		remCount %= DIGEST_SIZE;
	}

	/**
	 * Generates an integer containing the user-specified number of
	 * pseudo-random bits (right justified, with leading zeros).  This
	 * method overrides a <code>java.util.Random</code> method, and serves
	 * to provide a source of random bits to all of the methods inherited
	 * from that class (for example, <code>nextInt</code>,
	 * <code>nextLong</code>, and <code>nextFloat</code>).
	 *
	 * @param numBits number of pseudo-random bits to be generated, where
	 * 0 <= <code>numBits</code> <= 32.
	 */
	final protected int next(int numBits) {
		int numBytes = (numBits+7)/8;
		byte b[] = new byte[numBytes];
		int next = 0;

		nextBytes(b);
		for (int i=0; i<numBytes; i++)
			next = (next << 8) + (b[i] & 0xFF);

		return next >>> (numBytes*8 - numBits);
	}

	/**
	 * Returns the given number of seed bytes, computed using the seed
	 * generation algorithm that this class uses to seed itself.  This
	 * call may be used to seed other random number generators.  While
	 * we attempt to return a "truly random" sequence of bytes, we do not
	 * know exactly how random the bytes returned by this call are.  (See
	 * the empty constructor <a href = "#SecureRandom">SecureRandom</a>
	 * for a brief description of the underlying algorithm.)
	 * The prudent user will err on the side of caution and get extra
	 * seed bytes, although it should be noted that seed generation is
	 * somewhat costly.
	 *
	 * @param numBytes the number of seed bytes to generate.
	 *
	 * @return the seed bytes.
	 */
	public static byte[] getSeed(int numBytes) {
		byte[] retVal = new byte[numBytes];

		for (int i=0; i<numBytes; i++)
			retVal[i] = (byte) SeedGenerator.getByte();

		return retVal;
	}


	/**
	 * Helper function to convert a long into a byte array (least significant
	 * byte first).
	 */
	private static byte[] longToByteArray(long l) {
		byte[] retVal = new byte[8];

		for (int i=0; i<8; i++) {
			retVal[i] = (byte) l;
			l >>= 8;
		}

		return retVal;
	}
}
